1. Field of the Invention
The present invention relates to route searching methods and apparatus, and more particularly to a method and an apparatus for automatically selecting the most suitable route between a point of departure and a destination specified on a map.
2. Description of the Background Art
In recent years, with the development of electronics, the navigation apparatus for guiding vehicles have spread rapidly. Some conventional navigation apparatus are equipped with a route searching apparatus for automatically selecting the most suitable route from a starting point to a destination (the shortest distance route or the minimum time route.)
In the conventional route searching apparatus, methods for obtaining the most suitable route for guiding vehicles include the automatic vehicle guiding method disclosed in Japanese Patent Laying-Open No. 59-105113 (referred to as a first conventional art, hereinafter), for example. This first conventional art obtains the most suitable route between a starting point and a destination by using the Dijkstra method, one of the optimum route determining methods, from road network data representative of a network of roads. The theory of the Dijkstra method is described in "Data Structures and Algorithms" written by A. V. Aho et al. and translated by Yoshio Ono, Kabushiki Kaisha Baihu-kan, 1990, pp. 179-183, for example.
When searching for the most suitable route between arbitrary two points on a network of roads according to the first conventional art, the time for obtaining the route increases as the numbers of intersections and roads included in the road network increase. As a result, a user must wait for a longer time (e.g., about two or three minutes), which leads to inconvenience.
Hence, in order to reduce the calculating time, the so-called hierarchical route searching method is proposed in which the optimum route is obtained using map data having such a hierarchical structure as shown in FIG. 21. Such a hierarchical route searching method is disclosed in Japanese Patent Laying-Open No. 2-56591 (referred to as a second conventional art hereinafter) and Japanese Patent Laying-Open No. 3-54590 (referred to as a third conventional art hereinafter), for example. In these second and third conventional arts, as shown in FIG. 22, the lower hierarchical level .alpha.0 recording a detailed network of roads is searched and then the evaluation values which are used to search for the route, i.e., the costs (distance or travel time), are moved to the upper hierarchical level .alpha.1 having a rough network of roads by using common intersections recorded also an the upper hierarchical level .alpha.1. That is to say, the second and third conventional arts select the route by using detailed road network data in the vicinities of the starting point and the destination and by using thinned-out rough road network data (e.g., road network data excluding general roads other than national roads and free ways) in other regions.
The second and third conventional arts prepare data for showing cor respondence of common intersections which exist both in the upper and lower hierarchical road networks at the same positions. When shifting the search from the detailed road network data to the rough road network data, as shown in FIG. 23, the search is continued on the upper hierarchical level using the common intersection as a starting point for the search on the rough road network.
However, if the area searched on the detailed road network includes no intersections in common with the rough read network on the true most suitable route from the starting point to the destination, the selected route passes a common intersection deviated from the true most suitable route, as shown in FIG. 24. Accordingly, an abnormal route (a U-turn route or a bypass route) takes place in the vicinity of the intersection.
Accordingly, Japanese Patent Laying-Open No. 5-323870 (hereinafter referred to as a fourth conventional art) discloses the method in which the number of intersections used to shift the route search from the lower hierarchical level is increased on the upper hierarchical level road network data to prevent such an abnormal route (U-turn route or bypass route) as may take place in the second and third conventional arts. That is to say, in this fourth conventional art, intersections which exist on the detailed road network but appear merely as certain points on the roads on the rough road network can be used when shifting the searched road network data. That is to say, virtual intersections are provided on the roads on the rough road network at the same positions as the intersections on the detailed road network from which the search is shifted.
However, when setting such intersections for shifting the hierarchical level on the true most suitable route, it is not sufficient lo add a few intersections on the roads in the rough road network. As shown in FIG. 25, this requires that at least a dozen or so of intersections existing in its vicinity should be added. Accordingly, the number of intersections and the number of roads increase when searching the rough road network, resulting in an increase of the searching time.
Furthermore, the rough road network generally records rough configurations of roads to search a larger area than the detailed road network. Accordingly, precise positions can rot be obtained on the roads in the rough road network on the basis of the positions of intersections on the detailed road network. Hence, the fourth conventional art has the problem that the arrival cost from a halfway point on a road to the next intersection can not be correctly obtained on the rough road network and thus the correct most suitable route can not be obtained.